package cm.unit4.theme3;

import cm.commom.TreeNode;

import java.util.ArrayList;

public class FindPathDemo {
    ArrayList<ArrayList<Integer>> anslist = null;
    Integer targetSum = null;

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        anslist = new ArrayList<>();
        targetSum = target;
        ArrayList<Integer> list = new ArrayList<>();
        findPathHelper(root, list, 0, 0);

        return anslist;
    }

    void findPathHelper(TreeNode root, ArrayList<Integer> list, int deep, int sum) {
        if (root == null) {
            return;
        }

        if (root.left == null && root.right == null) {
            if (targetSum == sum + root.val) {
                list.add(root.val);
                anslist.add(new ArrayList<>(list));
                list.remove(deep);
            }
            return;
        }

        list.add(deep, root.val);
        findPathHelper(root.left, list, deep + 1, sum + root.val);
        list.remove(deep);

        list.add(deep, root.val);
        findPathHelper(root.right, list, deep + 1, sum + root.val);
        list.remove(deep);
    }
}
